Теорема о формуле чисел Стирлинга

$$ \begin{Bmatrix} n \\ k \end{Bmatrix} = \dfrac{\text{sur}(n,k)}{k!} = \dfrac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n $$

Пусть $B, C$ — множества, $|B| = n, |C| = k$. Любая сюрьекция $f \mathpunct{:} B \to C$ задает отношение эквивалентности $\sim_f$ на $B$, где $a \sim_f b \iff f(a) = f(b)$. Следовательно, $f$ задает разбиение $B$ на $k$ классов. Любое разбиение $B$ на $k$ классов можно задать сюрьекцией, «назначив» каждому классу свой элемент из $C$. Число сюрьекций, задающих фиксированное разбиение $B$ на $k$ классов, равно числу способов назначить классам элементы из $C$, то есть $k!$. Следовательно, получили, что $\begin{Bmatrix} n \\ k \end{Bmatrix} = \dfrac{\text{sur}(n,k)}{k!}$. $\square$